public class Leetcode {
}

//leetcode:134:加油站
class Solution1 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        for (int i = 0; i < n; i++) {//枚举所有的起点
            int rest = 0;//统计净收益
            for (int step = 0; step < n; step++) {//枚举每个起点走的步数，判断是否能够继续走到起点
                int index = (i + step) % n;//走step步后的下标
                rest += gas[index] - cost[index];
                if (rest < 0) {
                    //如果rest的值小于0，而我们知道i位置的元素一定大于0，那么我们i~i+step的值的和一定都是小于0的，所以我们就可跳过这些位置，直接跳到i+step+1处
                    i += step;
                    break;
                }
            }
            if (rest >= 0) {
                return i;
            }
        }
        return -1;
    }
}

//leetcode:738:单调递增序列
class Solution {
    public int monotoneIncreasingDigits(int n) {
        //把数字转换成字符数组
        char[] s = Integer.toString(n).toCharArray();
        int i = 0, m = s.length;

        //找到第一个递减位置
        while(i+1 < m && s[i] <= s[i+1]) i++;
        if(i == m - 1) return n;

        //如果最后一个递增位置的元素前面有连续且重复的这个数就进行回退
        while(i-1 >= 0 &&s[i] == s[i-1]) i--;

        //将这个位置的元素减1，然后将这位置后的所有元素都设置为9，这就保证一定是递增的
        s[i]--;
        for(int j = i+1; j < m; j++) s[j] = '9';

        //转换为数字返回
        return Integer.parseInt(new String(s));
    }
}

//leetcode:991:坏了的计算器
class Solution3 {
    //正难则反
    //从目标值转换为初始值
    public int brokenCalc(int startValue, int target) {
        int count = 0;
        while(startValue < target){
            //如果是偶数就进行除2
            if(target % 2 == 0){
                target /= 2;
            }else{
                //如果是奇数就进行加一
                target++;
            }
            //记录操作次数
            count++;
        }
        //如果进行上述操作后得到的值是小于/等于初始值的就让次数加上初始值减去此时的目标值
        return count + startValue - target;
    }
}